1. Field of the Invention
The present invention generally relates to digital halftoning and, more particularly, to a method and apparatus for halftoning which constructs and utilizes a dithering mask with memory requirements much smaller than the mask itself.
2. Background Description
Most printers today can print in only a limited number of colors. Digital halftoning is a technique for printing a picture (or more generally displaying it on some two-dimensional medium) using small dots with a limited number of colors such that it appears to consist of many colors when viewed from a proper distance. For example, a picture of black and white dots can appear to display grey levels when viewed from some distance.
The fastest and most commonly used methods for digital halftoning are dithering algorithms which use threshold arrays, also called dither matrices or dither masks. The original forms of these arrays used periodic patterns of threshold values which can have an unpleasant rendering at certain grey levels. This invention discloses a method and apparatus which halftones an image using a truly aperiodic mask, thus avoiding periodic patterns.
Concepts related to periodicity are central to this invention. Consequently, we first establish some terminology to be used through this discussion. In the formalism of standard mathematics we denote by the set of all real numbers, and by n-dimensional space. We also denote by Z the set of integers 0,.+-.1,.+-.2, . . . , and by Z.sup.n the set of n-tuples of integers. We call a function f from to periodic with period (p.sub.1,p.sub.2, . . . , p.sub.n) if for all (x.sub.1,x.sub.2, . . . , x.sub.n) in and (k.sub.1,k.sub.2, . . . k.sub.n).epsilon.Z.sup.n EQU f(x.sub.1 +k.sub.1 p.sub.1,x.sub.2 +k.sub.2 p.sub.2, . . . , x.sub.n +k.sub.n p.sub.n)=f(x.sub.1,x.sub.2, . . . , x.sub.n).
Periods are not unique. There may be a smaller period (q.sub.1, . . . , q.sub.n) where each q.sub.i is a factor of p.sub.i. We say a function from a hyper rectangle in is periodic if it is the restriction to of a periodic function.
Usually a page P is much bigger than a dithering mask M so that several copies of the mask are needed to cover the page. Thus, if the input image is a uniform grey, then the pattern of data generated by the mask is the restriction to P of a periodic function having one period given by the dimensions of the mask. It also might have smaller periods. Because of that in the context of printing one departs from mathematical usage and says that a mask is periodic if the patterns it yields for uniform grey levels have a period smaller than the size of the mask or if the mask is small itself in the sense that every threshold level is represented approximately once (e.g., a 16.times.16 mask to render 256 grey levels). Otherwise, the mask is usually called aperiodic which means there are no periods smaller than the one due to the size of the mask and the mask is big with respect to the number of grey levels to be rendered (e.g., a 128.times.128 mask to render 256 grey levels).
We shall disclose how to construct and utilize masks which are truly aperiodic in the sense that no subpattern is repeated periodically when rendering the various uniform greys on a page, not even a period the size of the mask, yet using only a small amount of memory.
One way to reduce memory requirements for a mask would be to generate random threshold values on the fly while printing. This requires more computation than a table lookup and comparison and would produce a much poorer quality output for two reasons:
One, too much randomness in the distribution of threshold values blurs the image. PA0 Two, blue noise, or noise with the low frequencies attenuated, gives the best visual effect, as described for instance in "Dithering with blue noise", Proc.IEEE 75, no.1 (1988) pp. 56-79, by R. Ulichney, and no method is known to generate blue noise on the fly by considering only the current pixel.
Methods to construct dithering masks with blue noise were proposed, for instance, in U.S. Pat. No. 5,111,310 to K. J. Parker and T. Mitsa, in "Digital halftoning using a blue noise mask", Proc. SPIE 1452 (1991) pp. 47-56, by T. Mitsa and K. J. Parker, and in "The void-and-cluster method for dither array generation", Proc. SPIE 1913 (1993) pp. 332-343, by R. Ulichney.
Once a mask is devised for halftoning greyscale pictures, previous art allows it to be used for color pictures. The individual color planes are halftoned using rotated periodic masks, in order to avoid a moire pattern, or other changes are made to masks such as described for instance in U.S. Pat. No. 5,341,228 to K. J. Parker and T. Mitsa in the case of a blue noise mask.
Most of these techniques and others are reviewed in the book Digital Halftoning, (MIT Press, Cambridge, Mass. 1987) by R. Ulichney, which is a general reference for digital halftoning.